package main

import (
	"data_struct/006queue"
	"fmt"
)

type Object interface{}

type node struct{
	data Object
	lchild *node 
	rchild *node
}

func main() {
	var a = &node{
		data : "A",
	}
	var b = &node{
		data : "B",
	}
	var c = &node{
		data : "C",
	}
	a.lchild = b;
	a.rchild = c;

	var d = &node{
		data : "D",
	}
	b.lchild=  d

	var e = &node{
		data : "E",
	}
	c.lchild = e 


	var f = &node{
		data : "F",
	}
	c.rchild = f 

	var g = &node{
		data : "G",
	}
	d.lchild = g

	var h = &node{
		data : "H",
	}
	d.rchild = h 

	var i = &node{
		data : "I",
	}
	e.lchild = i 

	// fmt.Println("a---", a.data, a.lchild.data, a.rchild.data)
	// PreOrder(a)
	// midOrder(a)
	// afterOrder(a)
	layerOrder(a)
}


//层序遍历
func layerOrder(BiTree *node){
	// 借助队列实现: 1 把根节点入队,   a 
	//2 弹出根节点 a , 并把 a结点的子结点 bc 入队
	//3弹出结点b , 把他的子节点加入队列,  
	// 如此操作, 直到队列为空
	q := queue.InitQueue();
	if BiTree.data != nil {
		//BiTree 前面加上* , 对 指针取值
		q.Push(*BiTree)
	}

	for !q.Empty(){
		n,_ := q.Pop();
		//强制转换一下类型
		node := n.(node);
		fmt.Print(node.data);
		if node.lchild != nil {
			q.Push(*node.lchild)
		}
		if node.rchild != nil {
			q.Push(*node.rchild)
		}
	}
}




func afterOrder(BiTree *node){
	//后序遍历左子树

	if BiTree.lchild != nil {
		afterOrder(BiTree.lchild)
	}

	//后序遍历右子树
	if BiTree.rchild != nil {
		afterOrder(BiTree.rchild)
	}

	//最后是自己
	if BiTree.data != nil {
		fmt.Print(BiTree.data)
	}
}

//PreOrder 中序遍历
func midOrder(BiTree *node)  {
	//先遍历左子树
	if BiTree.lchild != nil {
		midOrder(BiTree.lchild)
	}

	if BiTree.data != nil {
		fmt.Print(BiTree.data)
	}
	//再遍历右子树
	if BiTree.rchild != nil {
		midOrder(BiTree.rchild)
	}
}



//PreOrder 前序遍历
func PreOrder(BiTree *node)  {
	if BiTree.data == nil{
		fmt.Println("二叉树为空, 无法遍历");
		return ;
	}
	// 先展示当前结点的元素
	fmt.Print(BiTree.data)

	///再遍历左子树
	if BiTree.lchild != nil {
		PreOrder(BiTree.lchild)
	}

	//最后遍历右子树
	if BiTree.rchild != nil{
		PreOrder(BiTree.rchild)
	}
}